#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;


//method 1
int getMaxWidth(Tree *root)
{
    int ans = 0;
    queue<Tree *> myQue;
    if (!root) return ans;
    int curLevel = 1, nextLevel = 0;
    myQue.push(root);
    bool head = true;
    
    while(!myQue.empty()) {
        Tree *tmp = myQue.front();
        myQue.pop();
        if (!myQue.empty()) tmp->sibling = myQue.front();
        curLevel--;
        if (tmp->left) {
            myQue.push(tmp->left);
            nextLevel++;
        }
        if (tmp->right){
            myQue.push(tmp->right);
            nextLevel++;
        }
        if (curLevel == 0) {
            if (nextLevel > ans) 
                ans = nextLevel;
            tmp->sibling = NULL;
            head = true;
            curLevel = nextLevel;
            nextLevel = 0;
        }
    }
    return ans;
}

int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);

    result = getMaxWidth(root);
    cout <<"Max Width of the tree is " << result << endl;
}
